home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: LaTeX Document
(document/latex).
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 2a 20 46 49 42 4f 2e | 53 57 0d 0a 25 2a 2a 2a |%* FIBO.|SW..%***|
|00000010| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000020| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000030| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000040| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00000050| 2a 2a 2a 2a 2a 0d 0a 25 | 2a 09 09 09 09 09 09 09 |*****..%|*.......|
|00000060| 09 09 2a 0d 0a 25 2a 09 | 09 50 43 20 53 63 68 65 |..*..%*.|.PC Sche|
|00000070| 6d 65 2f 47 65 6e 65 76 | 61 20 34 2e 30 30 20 53 |me/Genev|a 4.00 S|
|00000080| 63 68 65 6d 65 20 63 6f | 64 65 09 09 09 2a 0d 0a |cheme co|de...*..|
|00000090| 25 2a 09 09 09 09 09 09 | 09 09 09 2a 0d 0a 25 2a |%*......|...*..%*|
|000000a0| 20 28 63 29 20 31 39 38 | 35 2d 31 39 38 38 20 62 | (c) 198|5-1988 b|
|000000b0| 79 20 54 65 78 61 73 20 | 49 6e 73 74 72 75 6d 65 |y Texas |Instrume|
|000000c0| 6e 74 73 2c 20 49 6e 63 | 2e 20 53 65 65 20 43 4f |nts, Inc|. See CO|
|000000d0| 50 59 52 49 47 48 54 2e | 54 58 54 09 09 2a 0d 0a |PYRIGHT.|TXT..*..|
|000000e0| 25 2a 20 28 63 29 20 31 | 39 39 32 20 62 79 20 4c |%* (c) 1|992 by L|
|000000f0| 2e 20 42 61 72 74 68 6f | 6c 64 69 20 26 20 4d 2e |. Bartho|ldi & M.|
|00000100| 20 56 75 69 6c 6c 65 75 | 6d 69 65 72 2c 20 55 6e | Vuilleu|mier, Un|
|00000110| 69 76 65 72 73 69 74 79 | 20 6f 66 20 47 65 6e 65 |iversity| of Gene|
|00000120| 76 61 09 2a 0d 0a 25 2a | 09 09 09 09 09 09 09 09 |va.*..%*|........|
|00000130| 09 2a 0d 0a 25 2a 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |.*..%*--|--------|
|00000140| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000150| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000160| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000170| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2a 0d 0a 25 |--------|----*..%|
|00000180| 2a 09 09 09 09 09 09 09 | 09 09 2a 0d 0a 25 2a 09 |*.......|..*..%*.|
|00000190| 09 53 6f 6d 65 20 66 75 | 6e 20 6f 6e 20 66 69 62 |.Some fu|n on fib|
|000001a0| 6f 6e 6e 61 63 63 69 20 | 6e 75 6d 62 65 72 73 09 |onnacci |numbers.|
|000001b0| 09 09 09 2a 0d 0a 25 2a | 09 09 09 09 09 09 09 09 |...*..%*|........|
|000001c0| 09 2a 0d 0a 25 2a 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |.*..%*--|--------|
|000001d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000200| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2a 0d 0a 25 |--------|----*..%|
|00000210| 2a 09 09 09 09 09 09 09 | 09 09 2a 0d 0a 25 2a 20 |*.......|..*..%* |
|00000220| 43 72 65 61 74 65 64 20 | 62 79 3a 20 4c 61 72 72 |Created |by: Larr|
|00000230| 79 20 42 61 72 74 68 6f | 6c 64 69 09 09 44 61 74 |y Bartho|ldi..Dat|
|00000240| 65 3a 20 31 39 39 32 09 | 09 09 2a 0d 0a 25 2a 20 |e: 1992.|..*..%* |
|00000250| 52 65 76 69 73 69 6f 6e | 20 68 69 73 74 6f 72 79 |Revision| history|
|00000260| 3a 09 09 09 09 09 09 09 | 2a 0d 0a 25 2a 09 09 09 |:.......|*..%*...|
|00000270| 09 09 09 09 09 09 2a 0d | 0a 25 2a 09 09 09 09 09 |......*.|.%*.....|
|00000280| 60 60 49 6e 20 6e 6f 6d | 69 6e 65 20 6f 6d 6e 69 |``In nom|ine omni|
|00000290| 70 6f 74 65 6e 74 69 69 | 20 64 65 69 27 27 09 2a |potentii| dei''.*|
|000002a0| 0d 0a 25 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |..%*****|********|
|000002b0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002c0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000002e0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 0d 0a 0d 0a 5c |********|***....\|
|000002f0| 64 6f 63 75 6d 65 6e 74 | 73 74 79 6c 65 5b 31 32 |document|style[12|
|00000300| 70 74 2c 61 34 2c 61 73 | 74 79 70 65 64 5d 7b 61 |pt,a4,as|typed]{a|
|00000310| 72 74 69 63 6c 65 7d 0d | 0a 5c 74 69 74 6c 65 7b |rticle}.|.\title{|
|00000320| 46 69 62 6f 6e 61 63 63 | 69 20 6e 75 6d 62 65 72 |Fibonacc|i number|
|00000330| 73 7d 0d 0a 5c 61 75 74 | 68 6f 72 7b 4c 61 72 72 |s}..\aut|hor{Larr|
|00000340| 79 20 42 61 72 74 68 6f | 6c 64 69 20 5c 26 20 68 |y Bartho|ldi \& h|
|00000350| 69 73 20 67 61 6e 67 7d | 0d 0a 5c 64 61 74 65 7b |is gang}|..\date{|
|00000360| 5c 74 6f 64 61 79 7d 0d | 0a 0d 0a 5c 6e 65 77 63 |\today}.|...\newc|
|00000370| 6f 6d 6d 61 6e 64 7b 5c | 70 63 73 7d 7b 7b 5c 73 |ommand{\|pcs}{{\s|
|00000380| 63 20 50 63 53 63 68 65 | 6d 65 7d 7d 0d 0a 0d 0a |c PcSche|me}}....|
|00000390| 5c 62 65 67 69 6e 7b 64 | 6f 63 75 6d 65 6e 74 7d |\begin{d|ocument}|
|000003a0| 0d 0a 5c 6d 61 6b 65 74 | 69 74 6c 65 0d 0a 0d 0a |..\maket|itle....|
|000003b0| 57 65 20 77 69 6c 6c 20 | 64 69 73 63 75 73 73 20 |We will |discuss |
|000003c0| 67 65 6e 65 72 61 74 69 | 6f 6e 20 6f 66 20 46 69 |generati|on of Fi|
|000003d0| 62 6f 6e 61 63 63 69 20 | 6e 75 6d 62 65 72 73 20 |bonacci |numbers |
|000003e0| 5b 7b 5c 73 63 20 4c 65 | 6f 6e 61 72 64 6f 20 64 |[{\sc Le|onardo d|
|000003f0| 61 20 50 69 73 61 7d 0d | 0a 69 6e 20 7b 5c 73 6c |a Pisa}.|.in {\sl|
|00000400| 20 4c 69 62 65 72 20 43 | 6f 6e 69 63 75 6c 6f 72 | Liber C|oniculor|
|00000410| 75 6d 7d 2c 20 76 6f 6c | 2e 20 49 2c 20 70 2e 20 |um}, vol|. I, p. |
|00000420| 32 38 33 2d 2d 32 38 34 | 5d 2e 0d 0a 54 68 69 73 |283--284|]...This|
|00000430| 20 66 61 6d 69 6c 79 20 | 6f 66 20 6e 75 6d 62 65 | family |of numbe|
|00000440| 72 73 20 69 73 20 72 65 | 63 75 72 73 69 76 65 6c |rs is re|cursivel|
|00000450| 79 20 64 65 66 69 6e 65 | 64 20 6f 76 65 72 20 24 |y define|d over $|
|00000460| 5c 63 61 6c 20 4e 24 20 | 62 79 0d 0a 24 24 46 5f |\cal N$ |by..$$F_|
|00000470| 30 20 3d 20 30 2c 20 46 | 5f 31 20 3d 20 31 2c 20 |0 = 0, F|_1 = 1, |
|00000480| 46 5f 6e 20 3d 20 46 5f | 7b 6e 2d 31 7d 20 2b 20 |F_n = F_|{n-1} + |
|00000490| 46 5f 7b 6e 2d 32 7d 2e | 24 24 20 4f 75 72 20 67 |F_{n-2}.|$$ Our g|
|000004a0| 6f 61 6c 20 69 73 20 74 | 6f 20 73 69 6d 75 6c 61 |oal is t|o simula|
|000004b0| 74 65 20 74 68 69 73 0d | 0a 70 72 6f 63 65 73 73 |te this.|.process|
|000004c0| 75 73 20 69 6e 20 5c 70 | 63 73 5c 20 63 6f 64 65 |us in \p|cs\ code|
|000004d0| 2c 20 61 6e 64 20 74 68 | 65 6e 20 74 6f 20 64 65 |, and th|en to de|
|000004e0| 72 69 76 65 20 61 20 63 | 6c 6f 73 65 64 20 66 6f |rive a c|losed fo|
|000004f0| 72 6d 20 66 6f 72 20 24 | 46 5f 6e 24 2e 0d 0a 0d |rm for $|F_n$....|
|00000500| 0a 48 65 72 65 20 77 6f | 75 6c 64 20 62 65 20 61 |.Here wo|uld be a|
|00000510| 20 66 69 72 73 74 20 74 | 72 79 3a 0d 0a 28 64 65 | first t|ry:..(de|
|00000520| 66 69 6e 65 20 28 66 69 | 62 6f 20 6e 29 20 28 69 |fine (fi|bo n) (i|
|00000530| 66 20 28 3c 20 6e 20 32 | 29 20 6e 0d 0a 09 09 20 |f (< n 2|) n.... |
|00000540| 20 20 20 20 28 2b 20 28 | 66 69 62 6f 20 28 2d 20 | (+ (|fibo (- |
|00000550| 6e 20 31 29 29 20 28 66 | 69 62 6f 20 28 2d 20 6e |n 1)) (f|ibo (- n|
|00000560| 20 32 29 29 29 29 29 0d | 0a 0d 0a 54 68 69 73 20 | 2))))).|...This |
|00000570| 69 73 20 61 20 76 65 72 | 79 20 70 6f 6f 72 20 61 |is a ver|y poor a|
|00000580| 6c 67 6f 72 69 74 68 6d | 20 69 6e 64 65 65 64 3a |lgorithm| indeed:|
|00000590| 20 7c 28 66 69 62 6f 20 | 6e 29 7c 20 72 69 73 65 | |(fibo |n)| rise|
|000005a0| 73 20 65 78 70 6f 6e 65 | 6e 74 69 61 6c 6c 79 0d |s expone|ntially.|
|000005b0| 0a 20 28 61 73 20 77 65 | 20 73 68 61 6c 6c 20 73 |. (as we| shall s|
|000005c0| 6f 6f 6e 20 73 65 65 29 | 2c 20 61 6e 64 20 74 68 |oon see)|, and th|
|000005d0| 65 20 61 6c 67 6f 72 69 | 74 68 6d 20 73 75 6d 73 |e algori|thm sums|
|000005e0| 20 6f 6e 65 73 20 61 6e | 64 20 7a 65 72 6f 65 73 | ones an|d zeroes|
|000005f0| 2c 20 73 6f 0d 0a 69 74 | 73 20 72 75 6e 6e 69 6e |, so..it|s runnin|
|00000600| 67 20 74 69 6d 65 20 69 | 73 20 6f 62 76 69 6f 75 |g time i|s obviou|
|00000610| 73 6c 79 20 65 78 70 6f | 6e 65 6e 74 69 61 6c 2e |sly expo|nential.|
|00000620| 0d 0a 0d 0a 41 20 62 65 | 74 74 65 72 20 6d 65 74 |....A be|tter met|
|00000630| 68 6f 64 20 63 6f 6d 65 | 73 20 66 72 6f 6d 20 74 |hod come|s from t|
|00000640| 68 65 20 6f 62 73 65 72 | 76 61 74 69 6f 6e 20 74 |he obser|vation t|
|00000650| 68 61 74 20 73 6f 6d 65 | 20 76 61 6c 75 65 73 20 |hat some| values |
|00000660| 61 72 65 20 63 6f 6d 70 | 75 74 65 64 0d 0a 6d 61 |are comp|uted..ma|
|00000670| 6e 79 20 74 69 6d 65 73 | 3a 20 7c 28 66 69 62 6f |ny times|: |(fibo|
|00000680| 20 30 29 7c 20 61 6e 64 | 20 7c 28 66 69 62 6f 20 | 0)| and| |(fibo |
|00000690| 31 29 7c 20 61 72 65 20 | 63 6f 6d 70 75 74 65 64 |1)| are |computed|
|000006a0| 20 72 6f 75 67 68 6c 79 | 0d 0a 7c 28 66 69 62 20 | roughly|..|(fib |
|000006b0| 6e 29 7c 20 74 69 6d 65 | 73 3b 20 61 6e 64 20 66 |n)| time|s; and f|
|000006c0| 69 67 75 72 65 73 20 64 | 65 63 72 65 61 73 65 20 |igures d|ecrease |
|000006d0| 72 61 70 69 64 6c 79 2e | 20 49 66 20 77 65 20 6d |rapidly.| If we m|
|000006e0| 65 6d 6f 72 69 7a 65 0d | 0a 74 68 65 20 76 61 6c |emorize.|.the val|
|000006f0| 75 65 73 20 6f 66 20 7c | 28 66 69 62 20 30 29 7c |ues of ||(fib 0)||
|00000700| 20 74 68 72 6f 75 67 68 | 20 7c 28 66 69 62 20 6e | through| |(fib n|
|00000710| 29 7c 2c 20 77 68 69 63 | 68 20 72 65 71 75 69 72 |)|, whic|h requir|
|00000720| 65 73 0d 0a 6c 69 6e 65 | 61 72 20 73 74 6f 72 61 |es..line|ar stora|
|00000730| 67 65 2c 20 74 68 65 20 | 65 78 65 63 75 74 69 6f |ge, the |executio|
|00000740| 6e 20 74 69 6d 65 20 62 | 65 63 6f 6d 65 73 20 6c |n time b|ecomes l|
|00000750| 69 6e 65 61 72 2e 20 49 | 6e 20 66 61 63 74 2c 20 |inear. I|n fact, |
|00000760| 77 65 20 63 61 6e 20 64 | 6f 20 65 76 65 6e 0d 0a |we can d|o even..|
|00000770| 62 65 74 74 65 72 2c 20 | 61 73 20 6f 6e 6c 79 20 |better, |as only |
|00000780| 74 68 65 20 6c 61 73 74 | 20 74 77 6f 20 65 76 61 |the last| two eva|
|00000790| 6c 75 61 74 69 6f 6e 73 | 20 61 72 65 20 6e 65 65 |luations| are nee|
|000007a0| 64 65 64 2e 20 54 68 69 | 73 20 69 73 20 74 72 69 |ded. Thi|s is tri|
|000007b0| 76 69 61 6c 6c 79 0d 0a | 63 6f 64 65 64 20 61 73 |vially..|coded as|
|000007c0| 3a 0d 0a 28 64 65 66 69 | 6e 65 20 28 66 69 62 20 |:..(defi|ne (fib |
|000007d0| 6e 29 0d 0a 20 20 28 64 | 65 66 69 6e 65 20 28 66 |n).. (d|efine (f|
|000007e0| 69 62 69 6e 74 65 72 6e | 20 61 30 20 61 31 20 6e |ibintern| a0 a1 n|
|000007f0| 29 0d 0a 20 20 20 20 28 | 69 66 20 28 3d 20 6e 20 |).. (|if (= n |
|00000800| 30 29 20 61 30 20 0d 0a | 20 20 20 20 20 20 20 20 |0) a0 ..| |
|00000810| 20 20 20 20 20 20 20 20 | 28 66 69 62 69 6e 74 65 | |(fibinte|
|00000820| 72 6e 20 61 31 20 28 2b | 20 61 30 20 61 31 29 20 |rn a1 (+| a0 a1) |
|00000830| 28 2d 31 2b 20 6e 29 29 | 29 29 0d 0a 20 20 28 66 |(-1+ n))|)).. (f|
|00000840| 69 62 69 6e 74 65 72 6e | 20 30 20 31 20 6e 29 29 |ibintern| 0 1 n))|
|00000850| 0d 0a 0d 0a 57 65 20 6e | 6f 77 20 77 61 6e 74 20 |....We n|ow want |
|00000860| 74 6f 20 61 70 70 72 6f | 78 69 6d 61 74 65 20 7c |to appro|ximate ||
|00000870| 28 66 69 62 20 6e 29 7c | 20 62 79 20 61 20 63 6c |(fib n)|| by a cl|
|00000880| 6f 73 65 64 20 66 6f 72 | 6d 2e 0d 0a 46 6f 72 20 |osed for|m...For |
|00000890| 74 68 61 74 20 70 75 72 | 70 6f 73 65 2c 20 6c 65 |that pur|pose, le|
|000008a0| 74 20 24 5c 78 69 24 2c | 20 24 5c 65 74 61 24 20 |t $\xi$,| $\eta$ |
|000008b0| 62 65 20 74 68 65 20 73 | 6f 6c 75 74 69 6f 6e 73 |be the s|olutions|
|000008c0| 20 6f 66 20 24 78 5e 32 | 20 2d 20 78 20 2d 20 31 | of $x^2| - x - 1|
|000008d0| 20 3d 20 30 24 2c 0d 0a | 61 6e 64 20 64 65 66 69 | = 0$,..|and defi|
|000008e0| 6e 65 0d 0a 24 24 5c 50 | 68 69 5f 6e 20 3a 3d 20 |ne..$$\P|hi_n := |
|000008f0| 5c 66 72 61 63 7b 5c 78 | 69 5e 6e 20 2d 20 5c 65 |\frac{\x|i^n - \e|
|00000900| 74 61 5e 6e 7d 7b 5c 78 | 69 5e 7b 2d 31 7d 20 2d |ta^n}{\x|i^{-1} -|
|00000910| 20 5c 65 74 61 5e 7b 2d | 31 7d 7d 2e 24 24 0d 0a | \eta^{-|1}}.$$..|
|00000920| 4f 62 76 69 6f 75 73 6c | 79 2c 20 24 5c 50 68 69 |Obviousl|y, $\Phi|
|00000930| 24 20 73 61 74 69 73 66 | 69 65 73 20 74 68 65 20 |$ satisf|ies the |
|00000940| 64 65 66 69 6e 69 6e 67 | 20 70 72 6f 70 65 72 74 |defining| propert|
|00000950| 69 65 73 20 6f 66 20 24 | 46 24 2c 20 61 6e 64 20 |ies of $|F$, and |
|00000960| 74 68 69 73 20 69 73 0d | 0a 74 68 65 20 65 78 70 |this is.|.the exp|
|00000970| 72 65 73 73 69 6f 6e 20 | 77 65 20 61 72 65 20 61 |ression |we are a|
|00000980| 66 74 65 72 2e 0d 0a 0d | 0a 54 6f 20 6d 61 6b 65 |fter....|.To make|
|00000990| 20 6d 61 74 74 65 72 73 | 20 6d 6f 72 65 20 63 6f | matters| more co|
|000009a0| 6d 70 6c 69 63 61 74 65 | 64 2c 20 74 68 6f 75 67 |mplicate|d, thoug|
|000009b0| 68 2c 20 77 65 20 6d 61 | 79 20 27 68 61 72 64 2d |h, we ma|y 'hard-|
|000009c0| 66 69 74 27 20 61 20 64 | 6f 75 62 6c 65 0d 0a 65 |fit' a d|ouble..e|
|000009d0| 78 70 6f 6e 65 6e 74 69 | 61 6c 20 6f 6e 74 6f 20 |xponenti|al onto |
|000009e0| 74 68 65 20 46 69 62 6f | 6e 61 63 63 69 20 73 65 |the Fibo|nacci se|
|000009f0| 71 75 65 6e 63 65 20 62 | 79 20 70 69 63 6b 69 6e |quence b|y pickin|
|00000a00| 67 20 6f 75 74 20 61 20 | 66 65 77 20 76 61 6c 75 |g out a |few valu|
|00000a10| 65 73 2e 0d 0a 4c 65 74 | 20 75 73 20 61 73 73 75 |es...Let| us assu|
|00000a20| 6d 65 20 77 65 20 6b 6e | 6f 77 20 74 68 65 20 62 |me we kn|ow the b|
|00000a30| 61 73 65 20 6f 66 20 74 | 68 65 20 74 77 6f 20 65 |ase of t|he two e|
|00000a40| 78 70 6f 6e 65 6e 74 69 | 61 6c 73 3a 0d 0a 28 64 |xponenti|als:..(d|
|00000a50| 65 66 69 6e 65 20 78 20 | 28 2f 20 28 2b 20 31 20 |efine x |(/ (+ 1 |
|00000a60| 28 73 71 72 74 20 35 29 | 29 20 32 29 29 0d 0a 28 |(sqrt 5)|) 2))..(|
|00000a70| 64 65 66 69 6e 65 20 79 | 20 28 2f 20 28 2d 20 31 |define y| (/ (- 1|
|00000a80| 20 28 73 71 72 74 20 35 | 29 29 20 32 29 29 20 0d | (sqrt 5|)) 2)) .|
|00000a90| 0a 0d 0a 50 69 63 6b 69 | 6e 67 20 6f 75 74 20 74 |...Picki|ng out t|
|00000aa0| 68 65 20 76 61 6c 75 65 | 73 20 6f 66 20 7c 28 66 |he value|s of |(f|
|00000ab0| 69 62 20 6d 29 7c 20 61 | 6e 64 20 7c 28 66 69 62 |ib m)| a|nd |(fib|
|00000ac0| 20 6e 29 7c 2c 20 77 65 | 0d 0a 73 6f 6c 76 65 20 | n)|, we|..solve |
|00000ad0| 74 68 65 20 6c 69 6e 65 | 61 72 20 65 71 75 61 74 |the line|ar equat|
|00000ae0| 69 6f 6e 20 73 79 73 74 | 65 6d 3a 0d 0a 28 64 65 |ion syst|em:..(de|
|00000af0| 66 69 6e 65 20 28 61 62 | 20 6d 20 6e 29 0d 0a 20 |fine (ab| m n).. |
|00000b00| 20 28 6c 65 74 20 28 28 | 78 5e 6d 20 28 65 78 70 | (let ((|x^m (exp|
|00000b10| 74 20 78 20 6d 29 29 20 | 28 78 5e 6e 20 28 65 78 |t x m)) |(x^n (ex|
|00000b20| 70 74 20 78 20 6e 29 29 | 0d 0a 09 28 79 5e 6d 20 |pt x n))|...(y^m |
|00000b30| 28 65 78 70 74 20 79 20 | 6d 29 29 20 28 79 5e 6e |(expt y |m)) (y^n|
|00000b40| 20 28 65 78 70 74 20 79 | 20 6e 29 29 20 0d 0a 20 | (expt y| n)) .. |
|00000b50| 20 20 20 09 28 66 69 62 | 6d 20 28 66 69 62 20 6d | .(fib|m (fib m|
|00000b60| 29 29 20 28 66 69 62 6e | 20 28 66 69 62 20 6e 29 |)) (fibn| (fib n)|
|00000b70| 29 29 0d 0a 20 20 20 20 | 28 6c 69 73 74 20 28 2f |)).. |(list (/|
|00000b80| 20 28 2d 20 28 2a 20 66 | 69 62 6d 20 79 5e 6e 29 | (- (* f|ibm y^n)|
|00000b90| 20 28 2a 20 66 69 62 6e | 20 79 5e 6d 29 29 0d 0a | (* fibn| y^m))..|
|00000ba0| 09 20 20 20 20 20 28 2d | 20 28 2a 20 78 5e 6d 20 |. (-| (* x^m |
|00000bb0| 79 5e 6e 29 20 28 2a 20 | 78 5e 6e 20 79 5e 6d 29 |y^n) (* |x^n y^m)|
|00000bc0| 29 29 20 0d 0a 20 20 20 | 20 20 20 20 20 20 20 28 |)) .. | (|
|00000bd0| 2f 20 28 2d 20 28 2a 20 | 66 69 62 6d 20 78 5e 6e |/ (- (* |fibm x^n|
|00000be0| 29 20 28 2a 20 66 69 62 | 6e 20 78 5e 6d 29 29 0d |) (* fib|n x^m)).|
|00000bf0| 0a 20 09 20 20 20 20 20 | 28 2d 20 28 2a 20 79 5e |. . |(- (* y^|
|00000c00| 6d 20 78 5e 6e 29 20 28 | 2a 20 79 5e 6e 20 78 5e |m x^n) (|* y^n x^|
|00000c10| 6d 29 29 29 29 29 29 0d | 0a 59 69 65 6c 64 69 6e |m)))))).|.Yieldin|
|00000c20| 67 20 61 20 6c 69 73 74 | 20 6f 66 20 74 77 6f 20 |g a list| of two |
|00000c30| 63 6f 65 66 66 69 63 69 | 65 6e 74 73 2c 20 74 68 |coeffici|ents, th|
|00000c40| 61 74 20 6f 66 20 7c 78 | 7c 20 61 6e 64 20 7c 79 |at of |x|| and |y|
|00000c50| 7c 0d 0a 72 65 73 70 65 | 63 74 69 76 65 6c 79 2e ||..respe|ctively.|
|00000c60| 20 54 68 65 73 65 20 74 | 77 6f 20 63 6f 65 66 66 | These t|wo coeff|
|00000c70| 69 63 69 65 6e 74 73 20 | 74 75 72 6e 20 6f 75 74 |icients |turn out|
|00000c80| 20 74 6f 20 62 65 20 62 | 6f 74 68 20 24 5c 73 71 | to be b|oth $\sq|
|00000c90| 72 74 7b 35 7d 24 2e 0d | 0a 0d 0a 41 20 66 69 72 |rt{5}$..|...A fir|
|00000ca0| 73 74 20 67 75 65 73 73 | 20 77 6f 75 6c 64 20 62 |st guess| would b|
|00000cb0| 65 20 74 6f 20 66 69 74 | 20 61 20 73 69 6d 70 6c |e to fit| a simpl|
|00000cc0| 65 20 65 78 70 6f 6e 65 | 6e 74 69 61 6c 20 74 6f |e expone|ntial to|
|00000cd0| 20 74 68 65 20 73 65 71 | 75 65 6e 63 65 2e 0d 0a | the seq|uence...|
|00000ce0| 54 68 69 73 20 69 73 20 | 64 6f 6e 65 20 62 79 20 |This is |done by |
|00000cf0| 74 68 69 73 20 72 6f 75 | 74 69 6e 65 2c 20 77 68 |this rou|tine, wh|
|00000d00| 6f 73 65 20 70 65 72 66 | 6f 72 6d 61 6e 63 65 20 |ose perf|ormance |
|00000d10| 69 73 20 61 63 63 65 70 | 74 61 62 6c 65 2c 20 65 |is accep|table, e|
|00000d20| 73 70 65 63 69 61 6c 6c | 79 0d 0a 66 6f 72 20 6c |speciall|y..for l|
|00000d30| 61 72 67 65 20 24 6e 24 | 2e 0d 0a 28 64 65 66 69 |arge $n$|...(defi|
|00000d40| 6e 65 20 28 66 69 62 61 | 20 6e 29 0d 0a 20 20 28 |ne (fiba| n).. (|
|00000d50| 2f 20 28 65 78 70 74 20 | 78 20 6e 29 20 28 73 71 |/ (expt |x n) (sq|
|00000d60| 72 74 20 35 29 29 29 0d | 0a 0d 0a 41 20 70 65 72 |rt 5))).|...A per|
|00000d70| 66 65 63 74 20 66 69 74 | 20 63 61 6e 20 62 65 20 |fect fit| can be |
|00000d80| 61 74 74 61 69 6e 65 64 | 20 69 66 20 77 65 20 63 |attained| if we c|
|00000d90| 61 72 65 20 74 6f 20 63 | 6f 6d 70 75 74 65 20 62 |are to c|ompute b|
|00000da0| 6f 74 68 20 65 78 70 6f | 6e 65 6e 74 69 61 6c 73 |oth expo|nentials|
|00000db0| 2e 0d 0a 54 68 65 20 72 | 65 73 75 6c 74 20 69 73 |...The r|esult is|
|00000dc0| 20 63 6f 72 72 65 63 74 | 20 74 6f 20 61 20 66 65 | correct| to a fe|
|00000dd0| 77 20 7b 5c 73 6c 20 75 | 6c 70 7d 20 65 76 65 6e |w {\sl u|lp} even|
|00000de0| 20 66 6f 72 20 73 6d 61 | 6c 6c 20 24 6e 24 2e 0d | for sma|ll $n$..|
|00000df0| 0a 28 64 65 66 69 6e 65 | 20 28 66 69 62 62 20 6e |.(define| (fibb n|
|00000e00| 29 0d 0a 20 20 28 2f 20 | 28 2d 20 28 65 78 70 74 |).. (/ |(- (expt|
|00000e10| 20 78 20 6e 29 20 28 65 | 78 70 74 20 79 20 6e 29 | x n) (e|xpt y n)|
|00000e20| 29 20 28 73 71 72 74 20 | 35 29 29 29 0d 0a 0d 0a |) (sqrt |5)))....|
|00000e30| 54 68 69 73 20 73 69 6d | 70 6c 65 20 63 6f 64 65 |This sim|ple code|
|00000e40| 20 77 69 6c 6c 20 63 6f | 6d 70 61 72 65 20 74 68 | will co|mpare th|
|00000e50| 65 20 64 6f 75 62 6c 65 | 2d 65 78 70 6f 6e 65 6e |e double|-exponen|
|00000e60| 74 69 61 6c 20 66 69 74 | 20 74 6f 20 74 68 65 0d |tial fit| to the.|
|00000e70| 0a 6f 72 69 67 69 6e 61 | 6c 20 73 65 71 75 65 6e |.origina|l sequen|
|00000e80| 63 65 20 61 6e 64 20 63 | 6f 6e 66 69 72 6d 20 6f |ce and c|onfirm o|
|00000e90| 75 72 20 70 72 65 64 69 | 63 74 69 6f 6e 73 2e 0d |ur predi|ctions..|
|00000ea0| 0a 28 64 65 66 69 6e 65 | 20 28 65 72 72 66 20 6e |.(define| (errf n|
|00000eb0| 29 0d 0a 20 20 28 2f 20 | 28 2d 20 28 66 69 62 20 |).. (/ |(- (fib |
|00000ec0| 6e 29 20 28 66 69 62 61 | 20 6e 29 29 20 28 66 69 |n) (fiba| n)) (fi|
|00000ed0| 62 20 6e 29 29 29 0d 0a | 0d 0a 5c 68 66 69 6c 6c |b n)))..|..\hfill|
|00000ee0| 20 57 72 69 74 74 65 6e | 20 77 69 74 68 20 5c 4c | Written| with \L|
|00000ef0| 61 54 65 58 20 61 6e 64 | 20 7b 5c 73 6c 20 53 63 |aTeX and| {\sl Sc|
|00000f00| 68 65 6d 65 57 45 42 7d | 2e 0d 0a 5c 65 6e 64 7b |hemeWEB}|...\end{|
|00000f10| 64 6f 63 75 6d 65 6e 74 | 7d 0d 0a 0d 0a 1a 0d 0a |document|}.......|
|00000f20| 1a | |. | |
+--------+-------------------------+-------------------------+--------+--------+
